package ViolenceRecursive;

/**
 * 背包问题：有限容量的背包如何装最贵的东西
 *
 * @author Liaorun
 */
public class knapsack {


    public static void main(String[] args) {
        System.out.println(maxValue1(new int[]{6, 7, 3, 1, 1}, new int[]{1, 100, 3, 1, 1}, 5));
        System.out.println(process2(new int[]{6, 7, 3, 1, 1}, new int[]{1, 100, 3, 1, 1}, 0, 0, 0, 5));
    }

    public static int maxValue1(int[] weights, int[] values, int bag) {
        return process1(weights, values, 0, 0, bag);
    }

    private static int process1(int[] weights, int[] values, int i, int alreadyWeight, int bag) {


        // 是否还有下一个货物
        if (i == weights.length) {
            // 没有就没有收益
            return 0;
        }

        if (alreadyWeight + weights[i] > bag) {
            // 加上当前的重量超过负重，就不要当前的货物尝试下一个
            return process1(weights, values, i + 1, alreadyWeight, bag);
        } else {
            // 加上当前的重量没有超过负重，就要尝试要和不要当前货物两种情况，最终只要收益大的那种
            return Math.max(process1(weights, values, i + 1, alreadyWeight, bag), values[i] + process1(weights, values, i + 1, alreadyWeight + weights[i], bag));
        }


    }

    public static int maxValue2(int[] c, int[] p, int bag) {
        int[][] dp = new int[c.length + 1][bag + 1];
        for (int i = c.length - 1; i >= 0; i--) {
            for (int j = bag; j >= 0; j--) {
                dp[i][j] = dp[i + 1][j];
                if (j + c[i] <= bag) {
                    dp[i][j] = Math.max(dp[i][j], p[i] + dp[i + 1][j + c[i]]);
                }
            }
        }

        return dp[0][0];
    }

    public static int process2(int[] weights, int[] values, int i, int alreadyWeight, int alreadyValue, int bag) {

        // 是否还有下一个货物
        if (i == values.length) {
            // 没有就没有收益
            return alreadyValue;
        }

        if (alreadyWeight + weights[i] > bag) {
            // 加上当前的重量超过负重，就不要当前的货物尝试下一个
            return process2(weights, values, i + 1, alreadyWeight, alreadyValue, bag);
        } else {
            // 加上当前的重量没有超过负重，就要尝试要和不要当前货物两种情况，最终只要收益大的那种
            return Math.max(process2(weights, values, i + 1, alreadyWeight, alreadyValue, bag), process2(weights, values, i + 1, alreadyWeight + weights[i], alreadyValue + values[i], bag));
        }

    }
}
